When a computer application provides data to a device for printing and/or display, an intermediate description of the page is often given to the device driver software in a page description language, such as PostScript™ or PCL, which provide descriptions of the objects to be rendered onto the page, rather than a raster image of the page to be printed. Equivalently, a set of descriptions of graphics objects may be provided in function calls to a graphics interface, such as the Graphics Device Interface (GDI) in the Microsoft Windows™ operating system, or the X-11 in the UniX™ operating system. The page is typically rendered for printing and/or display by an object-based graphics system (or Raster Image Processor).
Most of these object based graphics systems utilize a large area of memory, known to the art as a framestore or a page buffer, to hold a pixel-based image of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled and written into the framestore in sequence. For two-dimensional graphics, objects that appear in front of other objects are simply written into the framestore after the background objects, thereby replacing the background on a pixel by pixel basis. Higher priority graphic objects take precedence because they are drawn later than those of lower priority. This is commonly known to the art as “Painter's algorithm”. Objects are passed down through the graphics device interface in priority order, from the rearmost object to the foremost object. The rearmost object has the lowest priority (or z-order), and the foremost object has the highest priority (or z-order).
The usual conventions used to describe orientations on a page are shown in FIGS. 25A and 25B, for portrait and landscape pages respectively. Page 2504 has a portrait orientation and page 2508 is in landscape orientation. A three-dimensional coordinate system is used to describe directions. Typically the top left corner of the page is considered the origin. Across the page is an increasing x direction 2502, 2506, and down the page is an increasing y direction 2503, 2507. An axis 2501, 2505 comes out of the page in an increasing z direction. Even though pages 2504, 2508 are two-dimensional, it is useful to have a three dimensional coordinate system. Objects on the page can appear in front of and/or behind other objects so it is sometimes desirable to give objects a z-level to which reference can be made.
Typically, each object is rasterized in scanline order and pixels are written to the framestore in sequential runs (pixel spans) along each scanline. Some graphics interfaces allow a logical or arithmetic operation to be specified, which is performed between one or more graphics objects and the already rendered pixels in the framestore. In these cases, the principle remains the same; objects (or groups of objects) are rasterized in scanline order, and the result of the specified operation is calculated and written to the framestore in sequential runs along each scanline.
There are essentially two problems with this technique. The first is that the technique requires fast random access to all of the pixels in the framestore. This is because each new object could affect any pixel in the framestore. For this reason, the framestore is normally kept in semiconductor random access memory (RAM). For high-resolution color printers the amount of RAM required can be very large, typically in excess of 100 Mbytes, which is relatively costly and difficult to run at high speed. The second problem is that many pixels in the framestore are over-painted (re-rendered) by later objects, often many times. Painting these pixels with the earlier objects can result in considerable wasted computation effort and wasted memory bandwidth. Both result in lower rendering performance.
One method for overcoming the large framestore problem is the use of “banding”. When banding is used, only part of the framestore exists in memory at any one time. All of the objects to be drawn are retained in an object list by the rendering application. This object list is considered in object order as above, but the only pixel operations performed are those which fall within the part of the page intersected by the band. After all objects in the object list have been drawn, the band is complete, and can be sent to the printer (or to intermediate storage) and the process repeats for the next band on the page. With this method, the bands are rendered in order, down the page. There are some penalties with this technique, however. It is necessary to retain in a list all objects to be drawn on the page. It may also be necessary to reconsider the objects being drawn many times, possibly once for each band. As the number of bands increases, so too does the repetitious examination of the objects being rendered. Also, the technique of banding does not solve the problem of the cost of over-painting. In some implementations, the overhead of dividing the page into bands can also result in a performance penalty.
In some graphics systems implementing this banding method, the input graphics objects are first converted into a ‘simplified’ intermediate format, and stored in a “display list”. The format and ordering of this display list is chosen to make the rendering process more efficient. For example, the entries in the display list are usually sorted in terms of increasing y co-ordinates and then x co-ordinates. Such use of an intermediate display list can alleviate some of the problems described in earlier methods, but the over-painting problem remains.
Some other graphic systems consider the image in scanline order. Again, all of the objects on the page are retained in a list, which can be an intermediate display list. On each scanline the objects which intersect that scanline are considered in priority order and for each object, spans of pixels between the intersection points of the object edges with the scanline are filled in a line store. This technique overcomes the large framestore problem, but however still suffers from the over-painting problem.
Other graphic systems utilize pixel-sequential rendering to overcome both the large framestore problem and the over-painting problem. In these systems, each pixel is generated in raster order. Again, all objects to be drawn are retained in a list. On each scanline, the edges of objects which intersect that scanline, are held in increasing order of their intersection with the scanline. These points of intersection, or edge crossings, are considered in turn, and are used to decide whether the associated object is being ‘activated’ or ‘de-activated’ by the edge. The activation count toggles which object is the topmost object and allows only the contributing objects to be painted onto the page. Some objects may be transparent, in which case the transparent objects and objects lying directly below them in z-order need to be combined to yield the output pixel. This combination using the object's transparency is called Alpha compositing.
Alpha (α) compositing is a mechanism used in computer graphics and image processing as a means of overlaying and combining two layers of two-dimensional color data to obtain a single output layer. Each layer has an array of pixels, with each pixel being formed by a set of values or channels. In alpha compositing, one channel is always the “a channel”, which describes the opacity of the pixel to be reproduced. Opacity is the extent to which a pixel in a layer will override or obscure colour information from pixels on layers behind the layer in question. Opacity is often referred to by its conjugate name, transparency. In a normalised system, opacity=(1−transparency).
The remaining channels describe the colour of the pixel. The number of these remaining channels and the manner in which they describe the colour of the pixel is implementation specific. For example, there may be just one colour channel (in the case of greyscale or colour separated images), or there may be multiple colour channels (for example red, green and blue). These different ways of describing colour are often referred to as the colourspace of the image. It is assumed that the colourspace is the same for all pixels on a layer.
Graphic systems which use pixel-sequential rendering have significant advantages in that there is no framestore or line store and no unnecessary over-painting. Inherently less memory and less work in rendering is a result.
In pixel-sequential rendering systems, each scanline has to process edge crossings and determine which levels will be active for the next span. Generally this is done for every edge crossing for every scanline. The retrieval of the levels and sorting into the active level list may be an expensive and time-consuming process in the whole rendering pipeline. Typically, the level retrieval and sorting may consume 20% of the total render time. There is accordingly a need for more efficient methods for managing the lists of active levels.